package dfs_bfs.test756;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/8 16:47
 */
public class Solution1 {


    // DFS 深搜
    HashMap<String, List<Character>> map = new HashMap<>();

    public boolean pyramidTransition(String bottom, List<String> allowed) {
        for (String s : allowed) {
            String c1 = s.substring(0, 2);
            char c2 = s.charAt(2);
            List<Character> cur = map.getOrDefault(c1, new ArrayList<Character>());
            cur.add(c2);
            map.put(c1, cur);
        }
        return dfs(bottom, "");
    }

    private boolean dfs(String bottom, String now) {
        if (bottom.length() == 1) return true;

        if (now.length() + 1 == bottom.length()) return dfs(now, "");

        int n = now.length();
        String cur = bottom.substring(n, n + 2);
        if (!map.containsKey(cur)) {
            return false;
        }
        for (char c : map.get(cur)) {
            String temp = now + c;
            if (dfs(bottom, temp)) {
                return true;
            }
        }
        return false;
    }
}
